/*
https://leetcode.cn/problems/count-numbers-with-unique-digits/

*/
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        else if(n==1) return 10;
        int num=pow(10,n);
        string s=to_string(num);
        int m=s.size();
        vector<vector<int>> memo(m, vector<int>(1 << 10, -1));
        auto dfs = [&](auto&& dfs, int i, int mask, bool is_limit, bool is_num) -> int {
            if (i == m) {       
                return is_num; // is_num 为 true 表示得到了一个合法数字
            }
            if (!is_limit && is_num && memo[i][mask] != -1) {
                return memo[i][mask];   //算过了就直接将它返回
            }
            int res = 0;
            if (!is_num) { // 可以跳过当前数位
                res = dfs(dfs, i + 1, mask, false, false);
            }
            int up = is_limit ? s[i] - '0' : 9;
            int d = is_num ? 0 : 1;
            for (; d <= up; d++) {
                if ((mask >> d & 1) == 0) {   //成立，我们就将d填入第i位
                    res += dfs(dfs, i + 1, mask | (1 << d), is_limit && d == up, true);
                }
            }
            if (!is_limit && is_num) {
                memo[i][mask] = res; // 记忆化
            }
            return res;
        };
        return dfs(dfs, 0, 0, true, false)+1;


    }
};